/*
 * TouchGraph LLC. Apache-Style Software License
 *
 *
 * Copyright (c) 2002 Alexander Shapiro. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. The end-user documentation included with the redistribution,
 *    if any, must include the following acknowledgment:
 *       "This product includes software developed by
 *        TouchGraph LLC (http://www.touchgraph.com/)."
 *    Alternately, this acknowledgment may appear in the software itself,
 *    if and wherever such third-party acknowledgments normally appear.
 *
 * 4. The names "TouchGraph" or "TouchGraph LLC" must not be used to endorse
 *    or promote products derived from this software without prior written
 *    permission.  For written permission, please contact
 *    alex@touchgraph.com
 *
 * 5. Products derived from this software may not be called "TouchGraph",
 *    nor may "TouchGraph" appear in their name, without prior written
 *    permission of alex@touchgraph.com.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL TOUCHGRAPH OR ITS CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 * ====================================================================
 *
 */

package geovista.touchgraph.graphelements;

import java.util.Collection;
import java.util.Collections;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Vector;

import geovista.touchgraph.Edge;
import geovista.touchgraph.Node;
import geovista.touchgraph.TGException;

/**
 * GraphEltSet contains data about the graph's components. Currently the only
 * components are edges and nodes.
 * 
 * @author Alexander Shapiro
 * @author Murray Altheim (added support for IDs)
 * 
 */
public class GraphEltSet implements ImmutableGraphEltSet {

	protected transient Vector nodes;
	protected transient Vector edges;

	public transient int nodeCount; // Not really necessary. Keeps count of the
	// nodes added, and does not decrement when
	// nodes are deleted. Maybe should be kept, but given a more obscure name.

	/**
	 * The Hashtable containing references to the Node IDs of the current graph.
	 */
	protected transient Hashtable nodeIDRegistry = null;

	// ...........

	/** Default constructor. */
	public GraphEltSet() {
		nodes = new Vector();
		edges = new Vector();
		nodeIDRegistry = new Hashtable(); // registry of Node IDs
		nodeCount = 0;
	}

	// Node manipulation ...........................

	/** Return the Node at int <tt>index</tt>, null if none are available. */
	protected Node nodeAt(int i) {
		if (nodes.size() == 0) {
			return null;
		}
		return (Node) nodes.elementAt(i);
	}

	/** Return the number of Nodes in the cumulative Vector. */
	public int nodeNum() {
		return nodes.size();
	}

	/** Return the node IDs in the current list */
	// added by hardisty aug 20 2002
	public String[] getNodeIDs() {
		String[] ids = new String[nodes.size()];
		for (int i = 0; i < nodeNum(); i++) {
			Node n = (Node) nodes.get(i);
			ids[i] = n.getID();
		}
		return ids;
	}

	public Vector getNodes() {
		Vector returnVec = new Vector();
		returnVec.setSize(nodes.size());
		Collections.copy(returnVec, nodes);
		return returnVec;
	}

	/**
	 * Registers the Node <tt>node</tt> via its ID String <tt>id</tt>.
	 * 
	 * @param id
	 *            the ID of the object.
	 * @param node
	 *            the Node to be registered.
	 */
	// protected void registerNode( String id, Node node ) {
	// FIXME
	// }

	/**
	 * Add the Node <tt>node</tt> to the graph, and registers the Node via its
	 * ID. If no ID exists, no registration occurs.
	 */
	public void addNode(Node node) throws TGException {
		String id = node.getID();
		if (id != null) {
			if (findNode(id) == null) { // doesn't already exist
				nodeIDRegistry.put(id, node);
				nodes.addElement(node);
				nodeCount++;
			} else {
				throw new TGException(TGException.NODE_EXISTS, "node ID '" + id
						+ "' already exists.");
			}
		} else {
			throw new TGException(TGException.NODE_NO_ID, "node has no ID."); // could
			// be
			// ignored?
		}
	}

	/** Returns true if the graph contains the Node <tt>node</tt>. */
	public boolean contains(Node node) {
		return nodes.contains(node);
	}

	// Edge manipulation ...........................

	/** Return the Edge at int <tt>index</tt>, null if none are available. */
	protected Edge edgeAt(int index) {
		if (edges.size() == 0) {
			return null;
		}
		return (Edge) edges.elementAt(index);
	}

	/** Return the number of Edges in the cumulative Vector. */
	public int edgeNum() {
		return edges.size();
	}

	/** Add the Edge <tt>edge</tt> to the graph. */
	public void addEdge(Edge edge) {
		if (edge == null) {
			return;
		}
		if (!contains(edge)) {
			edges.addElement(edge);
			edge.from.addEdge(edge);
			edge.to.addEdge(edge);
		}
	}

	/**
	 * Add an Edge from Node <tt>from</tt> to Node <tt>to</tt>, with tension of
	 * int <tt>tension</tt>, returning the Edge.
	 */
	public Edge addEdge(Node from, Node to, int tension) {
		Edge edge = null;
		if (from != null && to != null) {
			edge = new Edge(from, to, tension);
			addEdge(edge);
		}
		return edge;
	}

	/** Returns true if the graph contains the Edge <tt>edge</tt>. */
	public boolean contains(Edge edge) {
		return edges.contains(edge);
	}

	/**
	 * Return the Node whose ID matches the String <tt>id</tt>, null if no match
	 * is found.
	 */
	public Node findNode(String id) {
		if (id == null) {
			return null; // ignore
		}
		return (Node) nodeIDRegistry.get(id);
	}

	/**
	 * Return a Collection of all Nodes whose label matches the String
	 * <tt>label</tt>, null if no match is found.
	 */
	public Collection findNodesByLabel(String label) {
		Vector nodelist = new Vector();
		for (int i = 0; i < nodeNum(); i++) {
			if (nodeAt(i) != null && nodeAt(i).getLabel().equals(label)) {
				nodelist.add(nodeAt(i));
			}
		}
		if (nodelist.size() == 0) {
			return null;
		}
		return nodelist;
	}

	/** Return an Edge spanning Node <tt>from</tt> to Node <tt>to</tt>. */
	public Edge findEdge(Node from, Node to) {
		for (int i = 0; i < from.edgeNum(); i++) {
			Edge e = from.edgeAt(i);
			if (e.to == to) {
				return e;
			}
		}
		return null;
	}

	/** Delete the Edge <tt>edge</tt>. */
	public boolean deleteEdge(Edge edge) {
		if (edge == null) {
			return false;
		}
		if (!edges.removeElement(edge)) {
			return false;
		}
		edge.from.removeEdge(edge);
		edge.to.removeEdge(edge);
		return true;
	}

	/** Delete the Edges contained within the Vector <tt>nodesToDelete</tt>. */
	public synchronized void deleteEdges(Vector edgesToDelete) {
		for (int i = 0; i < edgesToDelete.size(); i++) {
			deleteEdge((Edge) edgesToDelete.elementAt(i));
		}
	}

	/**
	 * Delete the Edge spanning Node <tt>from</tt> to Node <tt>to</tt>,
	 * returning true if successful.
	 */
	public boolean deleteEdge(Node from, Node to) {
		Edge e = findEdge(from, to);
		if (e != null) {
			return deleteEdge(e);
		}
		return false;
	}

	/** Delete the Node <tt>node</tt>, returning true if successful. */
	public boolean deleteNode(Node node) {
		if (node == null) {
			return false;
		}
		if (!nodes.removeElement(node)) {
			return false;
		}

		String id = node.getID();
		if (id != null) {
			nodeIDRegistry.remove(id); // remove from registry
		}

		for (int i = 0; i < node.edgeNum(); i++) {
			Edge e = node.edgeAt(i);
			if (e.from == node) {
				edges.removeElement(e); // Delete edge not used, because it
				// would change the node's edges
				e.to.removeEdge(e); // vector which is being iterated on.
			} else if (e.to == node) {
				edges.removeElement(e);
				e.from.removeEdge(e);
			}
			// No edges are deleted from node. Hopefully garbage collection will
			// pick them up.
		}
		return true;
	}

	/** Delete the Nodes contained within the Vector <tt>nodesToDelete</tt>. */
	public synchronized void deleteNodes(Vector nodesToDelete) {
		for (int i = 0; i < nodesToDelete.size(); i++) {
			deleteNode((Node) nodesToDelete.elementAt(i));
		}
	}

	/** Returns a random node, or null if none exist (for making random graphs). */
	public Node getRandomNode() {
		if (nodes.size() == 0) {
			return null;
		}
		int r = (int) (Math.random() * nodeNum());
		return nodeAt(r);
	}

	/** Return the first Node, null if none exist. */
	public Node getFirstNode() {
		if (nodes.size() == 0) {
			return null;
		}
		return nodeAt(0);
	}

	public Edge[] getAllEdges() {
		Edge[] allEdges = new Edge[edges.size()];
		int i = 0;
		for (Enumeration e = edges.elements(); e.hasMoreElements();) {
			allEdges[i] = (Edge) e.nextElement();
			i++;

		}
		return allEdges;
	}

	/** Clear all nodes and edges. */
	public synchronized void clearAll() {
		nodes.removeAllElements();
		edges.removeAllElements();
		nodeIDRegistry.clear();
		nodeCount = 0;
	}

	/**
	 * A way of iterating through all the nodes. Maybe too complex, and should
	 * be replaced by iterators.
	 */
	public synchronized void forAllNodes(TGForEachNode fen) {
		for (int i = 0; i < nodeNum(); i++) {
			Node n = nodeAt(i);
			fen.forEachNode(n);
		}
	}

	/** iterates through pairs of Nodes. */
	public synchronized void forAllNodePairs(TGForEachNodePair fenp) {
		for (int i = 0; i < nodeNum(); i++) {
			Node n1 = nodeAt(i);
			fenp.beforeInnerLoop(n1);
			for (int j = i + 1; j < nodeNum(); j++) {
				fenp.forEachNodePair(n1, nodeAt(j));
			}
			fenp.afterInnerLoop(n1);
		}
	}

	/** Iterates through Edges. */
	public synchronized void forAllEdges(TGForEachEdge fee) {
		for (int i = 0; i < edgeNum(); i++) {
			Edge e = edgeAt(i);
			fee.forEachEdge(e);
		}
	}

	/**
	 * Returns a hashtable of Node-Integer pairs, where integers are the minimum
	 * distance from the focusNode to any given Node, and the Nodes in the
	 * Hashtable are all within radius distance from the focusNode.
	 */
	public Hashtable calculateDistances(Node focusNode, int radius) {
		Hashtable distHash = new Hashtable();
		distHash.put(focusNode, new Integer(0));

		TGNodeQueue nodeQ = new TGNodeQueue();
		nodeQ.push(focusNode);

		while (!nodeQ.isEmpty()) {
			Node n = nodeQ.pop();
			int currDist = ((Integer) distHash.get(n)).intValue();

			if (currDist == radius) {
				break;
			}

			for (int i = 0; i < n.edgeNum(); i++) {
				Edge e = n.edgeAt(i);
				Node adjNode = e.getOtherEndpt(n);
				if (contains(e) && !distHash.containsKey(adjNode)) {
					nodeQ.push(adjNode);
					distHash.put(adjNode, new Integer(currDist + 1));
				}
			}
		}
		return distHash;
	}

} // end com.touchgraph.graphlayout.graphelements.GraphEltSet
